AVL in SML

AVL的SML实现

我们通过一个简单的数据结构(AVL平衡二叉树)，对比了函数式语言和命令式语言的区别和联系。并且，通过一些大样例的实验，分析函数式和命令式语言在运行速度方面的特点。

与命令式C语言对比

AVL平衡树是在BST的基础上，加入平衡操作得到的。具体来说，对于一棵AVL树的插入和删除操作，我们必须要保证树的平衡性，即某个节点的左右孩子的高度之差最多为1。由此，引入了旋转的操作，分别为左旋、右旋、双左旋和双右旋。

AVL定义

首先，需要定义这个数据结构。对于SML来说，提供了类似typedef和struct的语法，可以得到如下的定义：

1
2
3
4
type data = int;
type height = int;
datatype AVL = Leaf
            |  Node of AVL * data * height * AVL;

在C语言中，可以使用struct实现：

1
2
3
4
5
6
7
8
9
typedef struct avlNode {
    int height;
    long data;
    struct avlNode *left;
    struct avlNode *right;
} *AVLNodePtr;
typedef struct avl {
    AVLNodePtr root;
} AVL;

相较于C语言，没有了指针之类的结构，ML的定义要简单清晰很多。

AVL旋转操作

AVL相比BST，需要维护一个height的结构，以下是使用C和SML获得一个节点的高度的方法：

1
2
3
int height(AVLNodePtr T) {	// in C language
    return T ? T->height : -1;
}
1
2
fun getH Leaf = ~1	// in SML
  | getH (Node(_, _, h, _)) = h;

由于AVL的数据结构很基础，这里只看一个简单左旋例子：





对于这样的左旋方法，我们可以很容易的写出对应的C语言程序。

1
2
3
4
5
6
7
8
AVLNodePtr rotateLeft(AVLNodePtr rt) {	// in C language
    AVLNodePtr newRoot = rt->left;
    rt->left = newRoot->right;
    newRoot->right = rt;
    rt->height = maxH(height(rt->left), height(rt->right)) + 1;
    newRoot->height = maxH(height(newRoot->left), height(newRoot->right)) + 1;
    return newRoot;
}

从短短几行的代码可以看出，指针操作的清晰度还是差了些。虽然逻辑很简单，但还是有出错的风险。

不过，在SML中，就完全没有这个问题：

1
2
3
4
5
fun rotateLeft (Node((Node(ll, ld, lh, lr)), d, h, r)) = let
  val nRt = Node(lr, d, maxH(getH(lr), getH(r)) + 1, r)
in
  Node(ll, ld, maxH(getH(ll), getH(nRt)) + 1, nRt)
end

因为SML中没有重新赋值的概念，我们旋转一个节点，实质上就是利用各个部件通过重新排列生成一个新节点。代码十分的清晰直观。不过，这确实会带来一定的性能浪费，函数式内部实现了引用的机制，但是这里的new操作是必不可少的。诚然，这种思想，使用C语言确实也可以实现，但是会有相当多的代码处理内存管理的问题。ML中的垃圾回收机制彻底解放了程序员。

值得一提的是，以上函数运行在SML中，编译器会提示：match nonexhaustive。这是因为rotateLeft这个函数，参数是类型绑定的但没有穷举所有的情况，比如传参是个叶子结点的情况。不过我们永远不会在叶子结点的情况下调用这个函数，所以选择无视这个警告。

对于双左旋操作，SML就更加的简单，只要一行代码，就可以实现完整的功能：

1
fun doubleRotateLeft (Node(l, d, h, r)) = rotateLeft(Node(rotateRight(l), d, h, r));

平衡插入

剩下的任务，就是实现一个balance函数，每次删除或者插入节点的时候，都需要调用。在这个函数上，C语言和SML语言其实打成了平手。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
AVLNodePtr balance(AVLNodePtr rt) {	// in C language
    if (!rt) return NULL;
    if (height(rt->left) - height(rt->right) > 1) {
        if (height(rt->left->left) >= height(rt->left->right))
            rt = rotateLeft(rt);
        else
            rt = doubleRotateLeft(rt);
    }
    else if (height(rt->right) - height(rt->left) > 1) {
        if (height(rt->right->right) >= height(rt->right->left))
            rt = rotateRight(rt);
        else
            rt = doubleRotateRight(rt);
    }
    rt->height = maxH(height(rt->left), height(rt->right)) + 1;
    return rt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun balance Leaf = Leaf	// in SML language
  | balance (Node(l, d, h, r)) = let
            val rt = if getH(l) - getH(r) > 1 then
                        if getH(getL(l)) >= getH(getR(l)) then
                            rotateLeft(Node(l, d, h, r))
                        else doubleRotateLeft(Node(l, d, h, r))
                   	else if getH(r) - getH(l) > 1 then
                        if getH(getR(r)) >= getH(getL(r)) then
                            rotateRight(Node(l, d, h, r))
                        else doubleRotateRight(Node(l, d, h, r))
                    else Node(l, d, h, r)
          in
            Node(getL(rt), getD(rt), maxH(getH(getL(rt)), getH(getR(rt))) + 1, getR(rt))
          end

可以看出，二者代码量差不多，笔者SML水平有限，如果这里可以有更加优雅简洁的写法，希望提出建议。

最后，insert函数和search函数两者的思想差不多，不过C语言还是有内存管理麻烦的问题，程序员不得不将精力放在分配释放内存或者检测空指针上面，不太容易体现算法的结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
AVLNodePtr insertTreeNode(AVLNodePtr rt, long data) {	// in C language
    if (!rt) {
        rt = (AVLNodePtr)malloc(sizeof(struct avlNode));
        rt->data = data;
        rt->left = NULL;
        rt->right = NULL;
        rt->height = 0;
    }
    if (rt->data > data) {
        rt->left = insertTreeNode(rt->left, data);
    }
    else if (rt->data < data) {
        rt->right = insertTreeNode(rt->right, data);
    }
    return balance(rt);
}
AVLNodePtr searchTreeNode(AVLNodePtr rt, long data) {
    if (!rt) return NULL;
    if (rt->data == data) return rt;
    else if (rt->data > data) return searchTreeNode(rt->left, data);
    else return searchTreeNode(rt->right, data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
fun insert (data, Leaf) = Node(Leaf, data, 0, Leaf)	// in SML
  | insert (data, Node(l, d, h, r)) = let
    val rt = if d > data then Node(insert(data, l), d, h, r)
             else if d < data then Node(l, d, h, insert(data, r))
             else Node(l, d, h, r)
  in
    balance(rt)
  end
fun search (Leaf) data = 0
  | search (Node(l, d, h, r)) data = if (d = data) then 1
                                     else if (d > data) then search l data
                                     else search r data;

输入输出

在C语言中，测试方式十分的直接，稍微处理下文件输入输出即可。

但是在SML函数式语言中，测试起来就没有那么简单。幸好，SML并不是一个“纯粹”的函数式语言，还是提供了很多的输入输出函数。

比如，我们需要将最后的查找结果，打印到一个”output.sml”的文件，需要进行如下书写：

1
2
3
4
5
6
7
8
9
10
11
fun printToFile(outFile: string, list: int list) =
  let
    val outStream = TextIO.openOut outFile
    fun out(xs : int list) =  
          case xs of
              [] => (TextIO.closeOut outStream)
            | x::xs' => (TextIO.output(outStream, (Int.toString x ^ "\n")); out(xs'))
  in
    out(list)
  end;
printToFile("./output.sml", res);

这里首先打开文件，之后，使用函数的递归的方法，逐个的遍历结果表中的元素，将其转化为字符串以后打印。

测试

如何进行测试呢？这里可以使用高阶函数map和foldl。

之前讲过，foldl可以实现$f(\ldots f(f(e, x_1), x_2)\ldots x_n)$的效果，给出代码：

1
val tree = foldl insert Leaf [1,2,3,4,5,6,7,8];

这里的Leaf就是上面的$e$，使用这个高阶函数，可以从1到8的每个数字，加入到生成AVL树中。这个写法比C语言使用循环插入高级很多。

对于搜索来说，可以理解为将一个查询的数组转化为一个结果的数组，自然而然我们想到了使用map函数。不过使用map之前，需要保证search函数经过了柯里化的操作，如下：

1
val search = fn : AVL -> data -> int

之后，我们构造一个函数，这个函数以一个data为参数，返回一个int型的结果。如下所示：

1
2
val f = search tree;
val f = fn : data -> int

其中的tree是使用foldl生成的。

之后，就可以使用map函数，获得一个映射的结果：

1
2
val res = map f searchData;
val res = [1,0,1,0,0,1,0,...] : int list

效率对比

公平起见，我们随机的生成大的测试样例。为了测试AVL树的正确性，在插入的时候，从1开始递增的插入节点。如果这里使用了BST，那将会导致搜索树退化为链表，效率从$O(\lg n)$降低到$O(n)$。

之后，搜索随机的选择点，C和SML的函数打印出0(Not found)或者1(found)。使用diff命令比较结果。

在测试中，C和SML程序的输出结果完全一致，但是效率相差很大：

样例 AVL in C AVL in SML
随机插入10000，查询5000 0.021s 2.134s
顺序插入10000，查询5000 0.022s 2.121s
顺序插入10000，查询10000 0.023s 2.870s
顺序插入20000，查询10000 0.046s 4.906s
顺序插入100000，查询10000 0.101s Time out

可以看出，完全一致的输入使用C和使用SML，效率相差了100倍！！！

在最后样例中使用SML出现了Time out的情况，可能是出现了某些内存管理或者文件读写的问题，具体原因未知。

当然，上面SML代码，可能存在可以大幅优化的部分。也有可能SML在大样例的输入输出上封装过多的内容，时间过多花费在了I/O上面。

完整的工程以及测试样例生成工具可以在Github上下载。

总结

函数式语言凭借其独有的优点，日渐流行。并且其编程思想，也开始在C++、Java、Python、Swift等等主流语言的迭代更新中得到体现。这些语言或者使用了$\lambda$表达式，或者使用了闭包或者代码块之类的概念来实现这一思想。

但是，函数式语言，至少是SML在效率的表现上实在太差。虽然它提供了更好的封装、更加简洁优美的写法、更加不容易出错的类型检查和自动的垃圾回收机制，但是100倍的效率差距带来的影响还是比这些优点强烈得多。

所以，SML目前使用范围还是很有限，多用于教学和科研。可能在未来，纯粹的函数式或者纯粹的过程式都不存在，出现的将是二者的结合体，达到一个更好的平衡。

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

现就读于华中科技大学<br><br>2018加油<br><br>做咸鱼也要做最咸的一条<br>